٩(๑•̀ω•́๑)و
嗨，我是wec，今天是DAY 9。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定一個網格，每個格子都有一個非負數字，從左上角走到右下角，每次只能向右或向下走。要求找出從左上角到右下角的最小路徑和。

🔎 解題思路＆程式碼

1️⃣ 動態規劃

第1步： 初始化第一行（因為只能往下走，所以每個格子的值就是上面的值加上當前格子的數字）與第一列（因為只能往右走，所以每個格子的值就是左邊的值加上當前格子的數字）。
第2步： 對於其他格子，要從它的上面或左邊才能走到，所以比較這兩個格子的路徑和，選擇比較小的那一條，然後加上當前格子的數字。
第3步： 右下角的格子會存儲從左上角走到這裡的最小路徑和，那就是我們要找的答案。
程式碼：

def min_path_sum(grid)
  (1...grid.length).each { |i| grid[i][0] += grid[i - 1][0] }
  (1...grid[0].length).each { |j| grid[0][j] += grid[0][j - 1] }

  (1...grid.length).each do |i|
    (1...grid[0].length).each do |j|
      grid[i][j] += [grid[i - 1][j], grid[i][j - 1]].min
    end
  end

  grid[-1][-1]
end

🔎 總結

時間複雜度

動態規劃： 時間複雜度為O(m * n)，m為行n為列。
➡️ 這題的解題關鍵在於每一步都只需要考慮如何從上面或左邊走過來的最短路徑，這樣最後在右下角就會出現我們要找的答案，並且直接在原來的網格上進行計算，這樣就可以避免使用額外的空間啦～而且不管表格多大都只要遍歷一次就好，對於較大的數據來說也可以很快的就解決問題了(ﾉ◕ヮ◕)ﾉ*:･ﾟ✧！

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃朋友做的taco（超級好吃）。
明天要說：Ruby精選刷題！Medium路跑D-3(>∀･)⌒☆